COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	(DE EVAL (X ENV)
C00007 00003	3. In the presence of side-effects, it is useful to extend the syntax 
C00010 00004	8. Assuming a representation  of sets as sequences, write algorithms  for set  union,
C00014 ENDMK
C⊗;
(DE EVAL (X ENV)
  (COND ((IS-CONST X) (VAL X))
	((IS-VAR X) (LOOKUP X ENV))
	((IS-IF X) (IF (EVAL (PREM X) ENV)
		       (EVAL (CONSE X) ENV)
		       (EVAL (ANTE X) ENV)))
	((IS-LAM X) (MK-FUNARG (FORM X)	
			       (BODY X)
			       (ENV)))
	(T (APPLY (EVAL (FUN X) ENV)
		  (EVLIS (ARGS X) ENV)
		  ENV))))

(DE APPLY (FN EARGS ENV)
  (COND ((IS-PRIM FN) (DOIT FN EARGS))
	((IS-FUNARG FN) (EVAL (BODY FN)
			      (MK-ENV (FORM FN)
				      EARGS
				      ENV)))
(DE EVLIS (L ENV)
    (IF (NULL L) 
	( )
	(CONCAT (EVAL (FIRST L) ENV)
		(EVLIS (REST L) ENV))))

(DE LOOKUP (N ST)
  (COND ((NULL ST) error)
	((IN N (BLOCK ST)) (VALUE N (BLOCK ST)))
	(T (LOOKUP N (TAIL ST)))))

1. Consider the  code for LOOKUP;  it is basically  rotten: we use  IN to search  the
name-compoment of a block and, if a  match is found, we use VALUE (rather  magically,
in fact) to extract the value associated  with that name.  This requires that we  run
through a block TWICE if  a name is located (in  fact, VALUE duplicates much of  IN).
Rewrite LOOKUP (without assigment statements!) so that we traverse a block only once.

2. The reason for writing LOOKUP initially in this dreadful fashion was to illustrate
a common computing phenomenon: namely, if a computation gives "false" then we go away
and do something else; however,  if the computation gives  a non-false value them  we
want to do further processing on that value. For example in LOOKUP, we might expect a
new version of IN, called IN1, to  return either "false" --i.e. NIL-- or an  encoding
of the value associated with the name; in the latter case, we need only extract  that
value (--careful!  we must  be able to recognize  the difference between NIL  meaning
"no value found" and NIL as the current value for the name).  Less elegant  languages
resort to some kind of assignment statement to save the intermediate result.  indeed,
such a hack can also be done in LISP:

(DE LOOKUP (N ST)
  (COND ((NULL ST) error)
	((SETQ XX (IN1 N (BLOCK ST))) (EXTRACT XX))
	(T (LOOKUP N (TAIL ST)))))

...indeed ugly, because XX is not bound within the definition of lookup.  A  solution
to this difficult is outlined on page 255 of Anatomy:

test[<p>;<f>; <b>]  is defined  such that  if <p>  returns a  NIL value  then <b>  is
evaluated, otherwise the unary  function, <f> is  applied to the  value of <p>.   For
example,   (DE LOOKUP (N ST)
  		(IF (NULL ST) 
       		    error
       		    (TEST (IN1 N (BLOCK ST)) EXTRACT (LOOKUP N (TAIL ST)))))

The problem: extend the EVAL-APPLY pair to recognize and evaluate TEST expressions.
3. In the presence of side-effects, it is useful to extend the syntax 
(and semantics) of the language as follows:

a: a function body may contain several expressions:

	(DE FOO (X Y) e1 e2  ... en)

b: a conditional expression may have several actions for each predicate expression:

  (COND (p1 e11 e11 e12 ... e1n)
	(p2 e21 e22  .... e2m)
	   ... )

in each of these cases we wish  the expression sequence to be evaluated  sequentially
from left-to-right. Indicate what  changes must be made  to the evaluator to  reflect
these extensions.

4. One (at least one!) language feature that we have not implemented in our evaluator
is DE,  i.e.  the  semantics of  function  definition.  Assuming  that we  have  SETQ
defined, extend the evaluator to support DE

5. Given the following functions:

(DE PAIR (X Y)
	(LAMBDA (SEL) (IF (EQ SEL 0)
			   X
			   Y)))

(DE HEAD (X) (X 0))           and          (DE TAIL (X) (X 1))

evaluate:     (HEAD (PAIR 'A 'B))  and   (TAIL (PAIR 1 2))

6.  We wish to represent tree-structures whose nodes are either terminal, or  consist
of three items: a left branch, a right branch, and an "information" component, N:

		  N
		/   \
	       /     \
	      L       R

write abstract algorithms that encode the following orders of visitation:  (a)  L-R-N
(b) L-N-R, and (c) N-L-R. You  may use the results of  problem 3.  How much does  the
semantics of the language influence your solution.

Suggest a sequence implementation  of these trees  and supply appropriate  selectors,
recognizers, and constructors.

7. Consider the following definition:

(DE APPEND (X Y)
    (IF (NULL X)
	Y
	(CONCAT (FIRST X)
	        (APPEND (REST X) Y))))

prove that (APPEND X (APPEND Y Z)) ≡ (APPEND (APPEND X Y) Z)
8. Assuming a representation  of sets as sequences, write algorithms  for set  union,
intersection, and power set (the set of all subsets of a set).  Write a predicate  to
test for set membership.

9. Consider, the Towers  of Hanoi puzzle:  given three vertical rods  and a stack  of
discs on one rod, arranged by size such  that the largest is on the bottom; move  the
discs to the adjacent rod, subject to the constraints that only one disc may be moved
at a time, and no disc may be placed on top of a smaller disc.

Write a recursive algorithm to describe  the solution, and give a justification  that
your solution is correct.

10. Consider  a  language  for propositional logic:
    (1) a  potentially  infinite collection of names: p, r, q,  ...x, y, z, p1, ...; 
    (2) two constants, T, and  F;
and (3) logical functions ∧, ∨, ¬, ≡, 

subject to the following definitions:

(A) expressions of the language are defined as follows:
      1. a name or constant is an expression
      2. if α and β are expressions then ¬(α) (α)∨(β), (α)∧(β), and (α)≡(β) 
	   are expressions
      3. expressions are only made by application of rules 1. and 2.

(B) the functions are defined as follows:

α | ¬α		α  β | α∨β	α   β | α∧β		α  β | α≡β
------		----------  	------------		-----------
T |  F		T  T |  T	T   T |  T		T  T |  T
F |  T		T  F |  T	T   F |  F		T  F |  F
		F  T |  T	F   T |  F		F  T |  F
		F  F |	F	F   F |  F		F  F |  T

Give a sequence-representation for expressions of this language.  Write an algorithm,
TAUTOLOGY, of  one  argument <exp>,  where  <exp>  represents an  expression  in  the
language and TAUTOLOGY is to give T as value just in the case that <exp> has value  T
for all possible assignments of values to names appearing in <exp>.

For example:
   expression		value for TAUTOGOLY
	T			T
       p∨T			T
       p∧T			F 	(give p the value F)
   (p∧q)≡(q∧p)			T
   (¬¬p)≡p			T